#ifndef __INDEX_OBJECT_POOL_ALLOC_HPP__
#define __INDEX_OBJECT_POOL_ALLOC_HPP__
#include "mutex.hpp"
#include "lock.hpp"
#include <stdexcept>
#include <vector>
namespace vpm 
{
	namespace utils
	{
		template<typename T>
		struct ObjectBase
		{
			ObjectBase()
			{
				index = 0; 
				flag = false; //used or not
			}
			int index:30; 
			int flag:2;
			T obj;	
		};
		template <typename T> 
		class ObjectBaseAccess
		{
		public:
			static int get_object_index(ObjectBase<T> & obj)
			{
				return obj.index; 
			}
			static ObjectBase<T> & get_object_base(T & obj)
			{
				return (ObjectBase<T>&)(*((int *) (&obj) -1)); 
			}	
			static ObjectBase<T> * get_object_base(T * obj)
			{
				return (ObjectBase<T>*)((int *) obj -1); 
			}

			static ObjectBase<T> * set_object_flag(ObjectBase<T> * obj, int flag)
			{		
				obj->flag = flag; 
				return obj; 
			}
		};


		template<typename _Tp>
		class IndexObjectPoolAllocator
		{	
			enum 
			{
				POOL_INIT_SIZE      = 1000, 
				POOL_INCREASE_SIZE  = 50, //when pool is empty , increase size , also the segment size 
				POOL_MAX_SIZE       = 1000000,
			};
		public:
			typedef ObjectBase<_Tp>  object_t; 
			typedef object_t*        object_pointer;
			typedef const object_t * const_object_pointer; 
			typedef object_t&        object_reference;
			typedef const object_t&  const_object_reference;
			typedef object_t         object_value_type;

			typedef size_t     size_type;
			typedef ptrdiff_t  difference_type;
			typedef _Tp*       pointer;
			typedef const _Tp* const_pointer;
			typedef _Tp&       reference;
			typedef const _Tp& const_reference;
			typedef _Tp        value_type;

			template<typename _Tp1>
			struct rebind
			{ 
				typedef IndexObjectPoolAllocator<_Tp1> other; 
			};

			IndexObjectPoolAllocator() throw() :m_objects(POOL_MAX_SIZE)
			{
				m_totalSize =0; 
				m_readSize =0;
				m_writeSize =0; 
				m_segments = 0; 
				m_searchSegment =0; 
				for (int i=0; i < POOL_MAX_SIZE ; i++)
				{
					m_objects[i] = NULL; 
				}	
				inflate();
			}

			~IndexObjectPoolAllocator() throw() 
			{
				for (int i=0; i < POOL_MAX_SIZE ; i++)
				{
					if (m_objects[i] != NULL)
					{
						::operator delete (m_objects[i]);
					}
				}
				printf("Total Allocate size %d, Read Size %d, Write Size %d",m_totalSize ,m_readSize, m_writeSize);
			}

			pointer address(reference __x) const { return &__x; }

			const_pointer address(const_reference __x) const { return &__x; }

			// NB: __n is permitted to be 0.  The C++ standard says nothing
			// about what the return value is when __n == 0.
			_Tp* allocate(size_type __n= sizeof(value_type), const void* = 0)
			{
				_Tp* __ret = 0;
				if (__n)
				{
					if (__n <= this->max_size())
					{
						int idx = segment_search(); 
						if (idx >=0)
						{		
							m_readSize ++;
							__ret = &(m_objects[idx]->obj); 					
							return __ret; 				
						}	

						if (m_totalSize < POOL_MAX_SIZE - POOL_INCREASE_SIZE) 
						{					
							this->inflate(); //NOTICE here , the m_totalSize changed in the inflate 
							idx = segment_search(); 
							if (idx >=0)
							{
								__ret = &(m_objects[idx]->obj); 
								m_readSize ++;
								return __ret; 
							}
						}
						else 
						{
							throw std::bad_alloc(); 				
						}
					}
					else
					{
						throw std::bad_alloc(); 
					}
				}
				return __ret;
			}

			// __p is not permitted to be a null pointer.
			void deallocate(pointer __p, size_type __n= sizeof(value_type))
			{ 		
				object_pointer pbase = ObjectBaseAccess<_Tp>::get_object_base(__p); 
				pbase->flag = false; 
				m_writeSize  ++; 		
			}
			// 	int simple_search()
			// 	{
			// 		for (int i=0; i< m_totalSize ; i++)
			// 		{
			// 			if (!m_objects[i]->flag)
			// 			{					
			// 				return i; 
			// 			}
			// 		}
			// 		return -1; 
			// 	}

			int segment_search()
			{
				Lock lock(m_writeMutex);
				for (int i=0; i < m_segments; i++) //the loop here is just search all segments once 
				{
					int begin = m_searchSegment *POOL_INCREASE_SIZE; 
					int end = begin+ POOL_INCREASE_SIZE ;

					for (int j = begin; j < end ; j++)
					{
						assert(m_objects[j] != NULL );
						if (!m_objects[j]->flag)
						{			
							m_objects[j]->flag = true;
							return j; 
						}
					}	
					m_searchSegment =(m_searchSegment + 1) % m_segments ; 
				}
				return -1; 
			}

			// a little slower than segment_search , maybe for many function call. 
			int  binary_search()
			{			
				Lock lock(m_writeMutex);
				for (int i=0; i < m_segments; i++) //the loop here is just search all segments once 
				{
					int n = m_searchSegment *POOL_INCREASE_SIZE; 
					int ret  = binary_search(n , n+POOL_INCREASE_SIZE -1);
					if (ret >=0 )
					{
						m_objects[ret]->flag = true;
						return ret; 				
					}

					m_searchSegment =(m_searchSegment + 1) % m_segments ; 			
				}
				return -1; 		
			}

			int  binary_search(int begin, int end)
			{				
				int guard = (end + begin) >> 1;

				assert(m_objects[guard] != NULL );
				if (!m_objects[guard]->flag)
				{				
					return guard; 
				}

				if (guard == begin)
				{
					return -1; 
				}

				int ret = binary_search(begin,guard); 
				if (ret >= 0)
				{
					return ret; 
				}
				ret = binary_search(guard,end); 
				if (ret >= 0)
				{
					return ret; 
				}

				return -1; 
			}

			size_type max_size() const throw() 
			{ 
				return size_t(-1) / sizeof(_Tp); 
			}

			void construct(pointer __p, const _Tp& __val) 
			{ 
				new(__p) _Tp(__val); 
			} 
			void destroy(pointer __p) 
			{ 
				__p->~_Tp(); 
			}

		private:
			void inflate()
			{		
				Lock lock(m_writeMutex);
				for (int i = m_segments * POOL_INCREASE_SIZE; i < m_segments * POOL_INCREASE_SIZE + POOL_INCREASE_SIZE ;i++)
				{
					m_objects[i] = static_cast<object_pointer>(::operator new (sizeof(object_value_type)));			 
					m_objects[i]->index= i; 
					m_objects[i]->flag = false; 
				}
				m_segments ++; 
				m_totalSize = m_segments* POOL_INCREASE_SIZE;		
			}

			IndexObjectPoolAllocator(const IndexObjectPoolAllocator&) throw() 
			{

			}

			// not allow copy 
			template<typename _Tp1>
			IndexObjectPoolAllocator(const IndexObjectPoolAllocator<_Tp1>&) throw() 
			{

			}

			template<typename _Tp1>
			void operator = (const IndexObjectPoolAllocator<_Tp1>&) throw() 
			{

			}

			std::vector<object_pointer> m_objects;	
			Mutex m_writeMutex; 

			int m_readSize ;
			int m_writeSize; 
			int m_totalSize ;
			int m_segments; 
			int m_searchSegment;
		};

	}
}


#endif //
  
  
